Search results for "Chordal graph"
showing 10 items of 14 documents
Dynamic 2- and 3-connectivity on planar graphs
1992
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n log2n) time. This gives O(log2n) amortized time per deletion. The space required by all our data structures is O(n).
Neighbor-Distinguishing k-tuple Edge-Colorings of Graphs
2009
AbstractThis paper studies proper k-tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given.
On the chromatic number of disk graphs
1998
Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their different generalizations. For all these graphs including the most general class of the double disk (DD) graphs, it is shown that X(G) ≤ c.ω(G) for a constant c. Several coloring algorithms are analyzed for disk graphs, aiming to improve the bounds on X(G). We find that their worst-case performance expressed in the number of used colors is indeed reached in some instances.
Optical Routing of Uniform Instances in Cayley Graphs
2001
Abstract Abstract We consider the problem of routing uniform communication instances in Cayley graphs. Such instances consist of all pairs of nodes whose distance is included in a specified set U. We give bounds on the load induced by these instances on the links and for the wavelength assignment problem as well. For some classes of Cayley graphs that have special symmetry property (rotational graphs), we are able to construct routings for uniform instances such that the load is the same for each link of the graph.
On Sturmian Graphs
2007
AbstractIn this paper we define Sturmian graphs and we prove that all of them have a certain “counting” property. We show deep connections between this counting property and two conjectures, by Moser and by Zaremba, on the continued fraction expansion of real numbers. These graphs turn out to be the underlying graphs of compact directed acyclic word graphs of central Sturmian words. In order to prove this result, we give a characterization of the maximal repeats of central Sturmian words. We show also that, in analogy with the case of Sturmian words, these graphs converge to infinite ones.
Some properties of vertex-oblique graphs
2016
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a fun…
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
On the hardness of optimization in power-law graphs
2008
Our motivation for this work is the remarkable discovery that many large-scale real-world graphs ranging from Internet and World Wide Web to social and biological networks appear to exhibit a power-law distribution: the number of nodes y"i of a given degree i is proportional to i^-^@b where @b>0 is a constant that depends on the application domain. There is practical evidence that combinatorial optimization in power-law graphs is easier than in general graphs, prompting the basic theoretical question: Is combinatorial optimization in power-law graphs easy? Does the answer depend on the power-law exponent @b? Our main result is the proof that many classical NP-hard graph-theoretic optimizati…
Bounds for minimum feedback vertex sets in distance graphs and circulant graphs
2008
Graphs and Algorithms
Radio Labelings of Distance Graphs
2013
A radio $k$-labeling of a connected graph $G$ is an assignment $c$ of non negative integers to the vertices of $G$ such that $$|c(x) - c(y)| \geq k+1 - d(x,y),$$ for any two vertices $x$ and $y$, $x\ne y$, where $d(x,y)$ is the distance between $x$ and $y$ in $G$. In this paper, we study radio labelings of distance graphs, i.e., graphs with the set $\Z$ of integers as vertex set and in which two distinct vertices $i, j \in \Z$ are adjacent if and only if $|i - j| \in D$.